package org.example.Problem;

import java.util.Enumeration;

public class QuickSort {
    private int len;
    private int[] nums;
    private int check(int key,int l,int r){
        int l1 = l,r1 = r;
        while(l1<r1){
            while (r1>l1){
                if(nums[r1]<=nums[key]) break;
                r1--;
            }
            while (l1<r1) {
                if (nums[l1] > nums[key]) break;
                l1++;
            }
            int tmp = nums[r1];
            nums[r1] = nums[l1];
            nums[l1] = tmp;
        }
        int tmp = nums[key];
        nums[key] = nums[l1];
        nums[l1] = tmp;
        return l1;
    }
    private void sort(int key,int l,int r){
        if(l>=r) return ;
        int pos = check(l,l,r);
        if(pos == l) sort(l+1,l+1,r);
        else if(pos == r) sort(l,l,r-1);
        else{
            sort(l,l,pos-1);
            sort(pos+1,pos+1,r);
        }
    }
    public int[] run(int[] nums){
        this.len = nums.length;
        this.nums = nums;
        sort(0,0,len-1);
        return this.nums;
    }
}
